#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None


class Solution:
    """
    @param: A: an integer array
    @return: A tree node
    """
    def sortedArrayToBST(self, A):
        # write your code here
        return self.rec_build(A)

    def rec_build(self, sorted_array):
        if not sorted_array:
            return None

        # mid_idx = len(sorted_array)  // 2               # NOTE: 左边比右边高
        mid_idx = (len(sorted_array) - 1) // 2            # NOTE: 右边比左边高: 题目需要的答案
        left, mid_v, right = sorted_array[0:mid_idx], sorted_array[mid_idx], sorted_array[mid_idx+1:]

        root = TreeNode(mid_v)
        root.left, root.right = self.rec_build(left), self.rec_build(right)
        return root


def main():
    print("start main")
    s = Solution()
    ret = s.sortedArrayToBST([1,2,3,4,5,6,7])
    # ret = s.sortedArrayToBST([-1, 1])
    print(ret.val)
    print(ret.left.val)
    print(ret.right.val)

if __name__ == "__main__":
    main()
